#
# fusion.core.item
#
# Copyright 2007-2008 Helsinki Institute for Information Technology
# and the authors.
#
# Authors: Ken Rimey <rimey@hiit.fi>
#

# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

"""
Encoding for Tamper-Resistant Sharing

ETRS data comprises immutable items, organized into datasets.  Each
dataset defines a key-value dictionary.

An item is a list, whose first element is its type.  The currently
defined types are "root", "kv" (key-value), and "cancel".  Items are
serialized as canonical s-expressions (see fusion.lib.sexp).

Each dataset has exactly one root item.  The SHA-1 hash of its
serialization is the ID of the dataset.  We call it an information ID.

The element immediately following the type in a non-root item is
always the ID of the dataset to which the item belongs.

The remaining elements of any item are two-tuples called fields.  Each
specifies a unique field name and a field value.  The field value is
most often a string.  In some cases, it will itself be a serialized
s-expression.  The fields of an item must appear in alphabetical order
by field name.

Every item has a signature field ("sig").  Note that it is not
necessarily the last field.  The signature is over the serialized item
with the signature field removed.

A root item defines a dataset:

["root" ["public_key" public_key] ["salt" salt] ["sig" sig] ["value" value]]

The public key and signature are represented as serialized
s-expressions.  That is, they are simply strings.

    public_key - the public key of the owner of the dataset.

    salt - a string of random bytes.

    sig - signature by the owner of the dataset.

    value - a string specifying additional immutable information about
    the dataset, encoded as a JSON object.

A kv item defines (an update to) a key-value pair:

["kv" iid ["key" key] ["seq" seq] ["sig" sig] ["value" value]]

    iid - the information ID of the dataset to which the item belongs,
    represented as a 20-byte binary string.

    key - a list of one or more non-empty byte strings.  (This is
    currently the only field whose value is not a string.)

    seq - a sequence number, expressed in decimal.  This is a positive
    integer greater than the sequence numbers of any other items with
    the same key present in the local copy of the dataset when this
    item was originally created.

    sig - signature by the owner of the dataset or some other
    authorized public key.  Note that signatures include the
    fingerprint of the signing key.

    value - a byte string of arbitrary length.

Deleted keys are tracked using tombstones.  A tombstone is simply a kv
item without a value field:

["kv" iid ["key" key] ["seq" seq] ["sig" sig]]

Datasets can define groups of public keys using member items, which
are simply kv items with a key whose first element is "member".  The
second element of the key is the fingerprint of the nominated member
in hexadecimal.  (Although the canonical s-expression encoding
accomodates binary data, we prefer to avoid binary in keys, which are
exposed to higher layers.)

The owner of a dataset is always authorized to sign any item.  The
owner can also authorize other public keys to sign particular items.
The authorization can be effected either through a rights item stored
in the dataset, or through information included in the root item's
value.  A rights item is simply a kv item with a key whose first
element is "rights".  In general, all rights pertaining to a dataset
are granted directly or indirectly by the owner of the dataset.  See
rights.py for the details.

It is possible to grant signing rights for particular items to anyone
at all.  In this case, the signing key is included in the item in a
public-key field:

["kv" iid ["key" key] ["public_key" public_key]
      ["seq" seq] ["sig" sig] ["value" value]]

The public key field is also used in member items to specify the
member's public key.

["kv" iid ["key" ["member" fingerprint]] ["public_key" public_key]
      ["seq" seq] ["sig" sig] ["value" value]]

If this is not a tombstone, the value should be a JSON-encoded object.
If no additional information about the membership is to be specified,
the value can be the two-byte string "{}".  Member items can
accomodate a variety of possibilities for the semantics of membership.
The meaning of a value that is invalid JSON or does not represent a
dictionary is undefined.  This implementation treats such a value
identically to "{}".

The same conventions apply to the value of a rights item.

Each new kv item normally supersedes all previous items with the same
key in that dataset.  An exception is made for member and rights
items, however, so that history can be replayed correctly when
forwarding items from one node to another.  In general, superseded
versions are retained when a key is deleted or the value is updated if
and only if the first element of the key is "member" or "rights".

The third item type is a cancel item:

["cancel" iid ["sig" sig]]

A cancel item effectively supersedes all kv items in the dataset and
signals that the dataset is no longer in use.

In storing different kinds of items in a database, we have found it
convenient to view them as special cases of a universal item type with
a larger number of fields: type, iid, key, value, seq, public_key,
salt, and sig.  Absent fields are set to None, with the following
exceptions for a root or cancel item:

    iid - the information ID (SHA-1 hash of the serialized root item).
    key - the empty list.
    seq - "1" for a root item, "2" for a cancel item.
"""

from hashlib import sha1
from os import urandom
from binascii import hexlify, unhexlify

import simplejson

from fusion.lib.sexp import encode, decode
from fusion.core.identity import decode_identity
from fusion.core.signature import decode_signature
from fusion.db.util import to_sqlite_string, from_sqlite_string

def init_doctest():
    """Initialize variables referred to in the doctests."""
    global root1, kv1, kv2, kv3, kv4, kv5, rights, cancel
    global root2, member
    global items

    from fusion.core.identity import generate

    identity1 = generate()
    identity2 = generate()
    identity3 = generate()
    identity4 = generate()

    root1 = create_root_item(identity1)
    root2 = create_root_item(identity2, note='testing...')

    iid1 = root1.iid
    iid2 = root2.iid

    kv1 = create_kv_item(iid1, ['favorite', 'color'], 'blue', 1, identity1)
    kv2 = create_kv_item(iid1, ['favorite', 'color'], 'violet', 2, identity1)
    kv3 = create_kv_item(iid1, ['favorite', 'color'], None, 3, identity1)

    rights_key = ['rights', 'details not important here...']
    rights = create_kv_item(iid1, rights_key, '{}', 1, identity1)

    member_key = ['member', identity3.fingerprint]
    member = create_kv_item(iid2, member_key, '{}', 1, identity2, identity3)

    kv4 = create_kv_item(iid1, ['answer'], '42', 1, identity3)

    kv5 = create_kv_item(iid1, ['question'], 'hello?', 1, identity4, identity4)

    cancel = create_cancel_item(iid1, identity1)

    items = [root1, root2, kv1, kv2, kv3, kv4, kv5, rights, member, cancel]

class Item(object):
    """
    Abstract base class for root, kv, and cancel items

    Every item defines the following attributes: hash, type, iid, key,
    value, seq, public_key, salt, and sig.
    """
    value = None
    public_key = None
    salt = None
    _sexp = None                # Cached value

    def __cmp__(self, other):
        """
        >>> kv1 < kv2 < kv3
        True
        >>> cmp(root1, root1)
        0
        """
        return cmp(self.seq, other.seq) or cmp(self.hash, other.hash)

    @property
    def hash(self):
        """
        >>> len(root1.hash)
        20
        """
        sexp = self.encode()
        return buffer(sha1(sexp).digest())

    def is_root(self):
        """
        >>> [item.is_root() for item in items]
        [True, True, False, False, False, False, False, False, False, False]
        """
        return self.type == 'root'

    def is_rights(self):
        """
        >>> [item.is_rights() for item in items]
        [False, False, False, False, False, False, False, True, False, False]
        """
        return self.type == 'kv' and self.key[0] == 'rights'

    def is_member(self):
        """
        >>> [item.is_member() for item in items]
        [False, False, False, False, False, False, False, False, True, False]
        """
        return self.type == 'kv' and self.key[0] == 'member'

    def validate(self):
        """
        Check the validity of the item, but not the signature or authorization.

        Raises ValueError if there is a problem.

        >>> all(item.validate() is None for item in items)
        True
        """
        optional = (str, type(None))
        for field, what in ((self.type, str),
                            (self.iid, buffer),
                            (self.key, list),
                            (self.seq, int),
                            (self.value, optional),
                            (self.public_key, optional),
                            (self.salt, optional),
                            (self.sig, str)):
            if not isinstance(field, what):
                raise ValueError

        for part in self.key:
            if not isinstance(part, str) or not part:
                raise ValueError

        if self.seq < 1:
            raise ValueError

        if self.public_key:
            identity = decode_identity(self.public_key)
            if identity.strength < 1.0:
                raise ValueError

    def verify_signature(self, signing_item):
        """
        Return True if the signature is valid.

        The public key is retrieved from the specified signing item.

        >>> [item.verify_signature(root1) for item in items]
        [True, False, True, True, True, False, False, True, False, True]
        >>> [item.verify_signature(root2) for item in items]
        [False, True, False, False, False, False, False, False, True, False]
        >>> [kv4.verify_signature(item) for item in items]
        [False, False, False, False, False, False, False, False, True, False]
        >>> kv5.verify_signature(kv5)
        True
        """
        try:
            identity = signing_item.get_identity()
            sig = self.get_signature()
            return identity.verify(self.digest(), sig)
        except (LookupError, ValueError):
            return False

    def get_identity(self):
        """
        Decode the public key specified in the item.

        Raises LookupError if there is none.
        """
        if self.public_key:
            return decode_identity(self.public_key)
        else:
            raise LookupError

    def get_signature(self):
        """Decode the item's signature."""
        return decode_signature(self.sig)

    def digest(self):
        """Return a hash over the item, excluding the signature."""
        sexp = self._encode(omit_signature=True)
        return sha1(sexp).digest()

    def encode(self):
        """Return a string encoding the item as a canonical s-expression."""
        if self._sexp is None:
            assert self.sig
            self._sexp = self._encode()
        return self._sexp

class RootItem(Item):
    def __init__(self, public_key, salt, sig, value):
        self.type = 'root'
        self.key = []
        self.seq = 1

        self.public_key = public_key
        self.salt = salt
        self.sig = sig
        self.value = value

    @property
    def iid(self):
        return buffer(self.hash)

    def validate(self):
        Item.validate(self)
        if not self.public_key or not self.salt or not self.value:
            raise ValueError

    def verify_signature(self, signing_item):
        if self.public_key != signing_item.public_key:
            return False
        return Item.verify_signature(self, signing_item)

    field_names = sorted(['public_key', 'salt', 'sig', 'value'])

    def _encode(self, omit_signature=False):
        data = [self.type]
        for name in self.field_names:
            if name != 'sig' or not omit_signature:
                value = getattr(self, name)
                if value is not None:
                    data.append((name, value))
        return encode(data)

class KVItem(Item):
    def __init__(self, iid, key, seq, sig, value=None, public_key=None):
        self.type = 'kv'
        self.iid = iid
        self.key = key
        self.seq = stdint(seq)
        self.sig = sig
        self.value = value
        self.public_key = public_key

    def validate(self):
        Item.validate(self)

        if not self.key:
            raise ValueError

        if self.is_member():
            type, fp = self.key
            pubkey = self.public_key
            if pubkey is not None and sha1(pubkey).hexdigest() != fp:
                raise ValueError

    field_names = sorted(['key', 'value', 'seq', 'public_key', 'sig'])

    def _encode(self, omit_signature=False):
        data = [self.type, str(self.iid)]
        for name in self.field_names:
            if name != 'sig' or not omit_signature:
                value = getattr(self, name)
                if value is not None:
                    if isinstance(value, int):
                        value = str(value)
                    data.append((name, value))
        return encode(data)

class CancelItem(Item):
    def __init__(self, iid, sig):
        self.type = 'cancel'
        self.key = []
        self.seq = 2

        self.iid = iid
        self.sig = sig

    def _encode(self, omit_signature=False):
        data = [self.type, str(self.iid)]
        if not omit_signature:
            data.append(("sig", self.sig))
        return encode(data)

def create_root_item(identity, **kwargs):
    """Construct a new RootItem."""
    pubkey = identity.encode_public()
    salt = urandom(20)
    value = simplejson.dumps(kwargs, sort_keys=True)
    item = RootItem(pubkey, salt, None, value)
    sig = identity.sign(item.digest())
    item.sig = sig.encode()
    item.validate()
    return item

def create_kv_item(iid, key, value, seq, identity, reference_identity=None):
    """
    Construct a KVItem.

    iid -- information ID as a binary buffer or hexadecimal string.
    key -- list of strings.
    value -- string or None.
    seq -- positive integer.
    identity -- signing Identity instance.
    reference_identity -- public key to be included in item (for
    member items and self-signed items).
    """
    iid = hex_to_buffer(iid)
    pubkey = (reference_identity.encode_public()
              if reference_identity else None)
    item = KVItem(iid, key, seq, None, value, pubkey)
    sig = identity.sign(item.digest())
    item.sig = sig.encode()
    item.validate()
    return item

def create_cancel_item(iid, identity):
    """Construct a CancelItem."""
    iid = hex_to_buffer(iid)
    item = CancelItem(iid, None)
    sig = identity.sign(item.digest())
    item.sig = sig.encode()
    item.validate()
    return item

def decode_item(string):
    """
    Construct an Item from a canonical s-expression.

    >>> all(decode_item(item.encode()) == item for item in items)
    True
    """
    data = decode(string)
    if len(data) < 2:
        raise ValueError

    type = data.pop(0)
    if type != 'root':
        iid = data.pop(0)
        if not isinstance(iid, str):
            raise ValueError
        iid = buffer(iid)

    if not all(isinstance(field, list) for field in data):
        raise ValueError

    previous = ''
    for name, value in data:
        if not isinstance(name, str) or not previous < name:
            raise ValueError
        previous = name

    fields = dict(data)
    try:
        if type == 'root':
            item = RootItem(**fields)        # Can raise TypeError.
        elif type == 'kv':
            item = KVItem(iid, **fields)     # Can raise TypeError.
        elif type == 'cancel':
            item = CancelItem(iid, **fields) # Can raise TypeError.
        else:
            raise ValueError
    except TypeError:
        raise ValueError

    item.validate()
    return item

def row_from_item(item):
    """
    Generate a database row from an Item.

    This function is specific to the "items" sqlite table defined in
    fusion.db.sqlite_db.
    """
    size = None if item.value is None else len(item.value)
    total_size = len(item.encode())
    row = (None, item.hash, item.type, item.iid,
           encode(item.key), item.value, item.seq, item.salt,
           item.public_key, item.sig, size, total_size)
    return tuple(map(to_sqlite_string, row))

def item_from_row(row):
    """
    Construct an Item from a database row.

    This function is specific to the "items" sqlite table defined in
    fusion.db.sqlite_db.

    >>> all(item_from_row(row_from_item(item)) == item for item in items)
    True
    """
    (num, hash, type, iid,
     key, value, seq, salt,
     public_key, sig, size, total_size) = map(from_sqlite_string, row)

    iid = buffer(iid)
    key = decode(key)

    if type == 'root':
        item = RootItem(public_key, salt, sig, value)
    elif type == 'kv':
        item = KVItem(iid, key, seq, sig, value, public_key)
    elif type == 'cancel':
        item = CancelItem(iid, sig)
    else:
        raise ValueError

    assert row_from_item(item)[1:] == row[1:]
    item.validate()

    item.num = num
    return item

def stdint(x):
    """
    Parse a decimal number and check that it is in canonical form.

    The argument can be either a string or an integer.  If it is a
    non-canonical decimal (e.g., if it has leading or trailing
    whitespace or leading zeros), raise ValueError.

    >>> stdint(42)
    42
    >>> stdint("42")
    42
    >>> stdint(" 42")
    Traceback (most recent call last):
        ...
    ValueError
    >>> int(" 42")
    42
    """
    i = int(x)
    if i == x or str(i) == x:
        return i
    else:
        raise ValueError

def hex_to_buffer(x):
    """
    Convert a hexadecimal string into a binary buffer.

    If the argument is already a buffer, it is returned as-is.

    >>> hexlify(hex_to_buffer(hex_to_buffer('abcd')))
    'abcd'
    """
    return x if isinstance(x, buffer) else buffer(unhexlify(x))

def hex(x):
    """
    Return the argument after checking that it is hexadecimal.

    The return value will always be a byte string and use lower case,
    even if the argument is unicode or includes upper case letters.

    Furthermore, if the argument is of buffer type, it is interpreted
    as binary data and converted to hexadecimal.

    >>> hex(hex(hex_to_buffer('abcd')))
    'abcd'
    """
    if isinstance(x, buffer):
        return hexlify(x)
    else:
        return hexlify(unhexlify(x))

if __name__ == '__main__':
    import doctest
    init_doctest()
    doctest.testmod()
